package q29_divide;


public class Solution_2 {
    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.println(i & 1);
        }
    }

    /**
     * 该方法需要用到移位操作，即>>>运算符，但在计算机中，该运算符实际上不等同于除法
     * 例如使用
     * @param dividend
     * @param divisor
     * @return
     */
    public static int divide(int dividend, int divisor) {
// 考虑被除数为最小值的情况
        if (dividend == Integer.MIN_VALUE) {
            if (divisor == 1) {
                return Integer.MIN_VALUE;
            }
            if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
        }
        // 考虑除数为最小值的情况
        if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (dividend == 0) {
            return 0;
        }

        // 一般情况，使用二分查找
        // 将所有的正数取相反数，这样就只需要考虑一种情况
        boolean rev = false;
        if (dividend > 0) {
            dividend = -dividend;
            rev = !rev;
        }
        if (divisor > 0) {
            divisor = -divisor;
            rev = !rev;
        }

        /*
        这种方法相当于在使用二分法在0到Integer.MAX_VALUE之间找出来一个数
        比如，当我们需要寻找X/Y的答案(这里先假设都是正数，容易理解)，那么假设X/Y = Z 有 Z * Y = X
        所以找出来的数Z`，就会有 Z` * Y <= X 且 (Z` + 1) & Y > X
        但是从0一直找到Integer.MAX_VALUE显然是不科学的，因此采用了二分法来进行查找
        同时，从绝对值的角度上来看，int的范围中负数的绝对值是大一些的，因此将两者都转为负数就能够规避一些溢出的问题
        所以就有了以下的这种解法：
        先定一个mid（中间值）如果这个数乘以除数比被除数大，就要将mid设置到right，否则就可以先将mid赋值给ans，并设置到left，然后继续找更大的
         */
        int left = 1, right = Integer.MAX_VALUE, ans = 0;
        while (left <= right) {
            // 注意溢出，并且不能使用除法
            // >> 1 该符号就是右移一位，代表着除以2的1次方的意思，这与直接的除法存在区别，具有底层的支持， >> n 也能够代表除以2的n次方
            int mid = left + ((right - left) >> 1);
            boolean check = quickAdd(divisor, mid, dividend);
            if (check) {
                ans = mid;
                // 注意溢出
                if (mid == Integer.MAX_VALUE) {
                    break;
                }
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return rev ? -ans : ans;

    }

    private static boolean quickAdd(int y, int z, int x) {
        // x 和 y 是负数，z 是正数
        // 需要判断 z * y >= x 是否成立
        int result = 0, add = y;
        while (z != 0) {
            // z & 1代表判断z是否为偶数 如果是偶数 则其为0 奇数则是1
            if ((z & 1) != 0) {
                // 需要保证 result + add >= x
                if (result < x - add) {
                    return false;
                }
                result += add;
            }
            if (z != 1) {
                // 需要保证 add + add >= x
                if (add < x - add) {
                    return false;
                }
                add += add;
            }
            // 不能使用除法
            // 但这个代表除以2
            z >>= 1;
        }
        return true;

    }
}
